This invention relates generally to multi-class digital networks and, in particular, to methods and apparatus for the distributed control of a multi-class digital network in order to efficiently adapt to rapid fluctuations in traffic load and service demand.
A multi-class digital network must accommodate traffic having different characteristics, quality of service (QOS) requirements, and transport modes. For example, a multi-class backbone network may be required to support both connection-based traffic and connectionless traffic. Further complication is introduced by the fact that within each category the traffic may include several classes differentiated by their characteristics and service requirements. The traffic classes may require different and possibly conflicting controls in order to satisfy service commitments and ensure acceptable service quality.
Asynchronous Transfer Mode (ATM) switching technology was developed to provide multi-service digital transport. It was assumed that ATM networks would provide the flexibility and quality of service required to satisfy the demand for digital services.
One disadvantage of ATM networks is that they are adapted to transport packets of only one size and format. Consequently, the packets of services which do not use ATM format must be deconstructed on admission to the ATM network by network edge devices and reconstructed by network edge devices on egress from the ATM network. This slows service delivery, increases computational requirements and complicates the structure and functionality of edge device interfaces.
The varying service requirements in a multi-class network are difficult to satisfy without traffic segregation and network partitioning. For example, certain services such as voice and video are somewhat loss tolerant but delay intolerant, while other services such as the exchange of data packets between computers are quite delay tolerant but completely loss intolerant. In accommodating such variations in service, a multi-service network naturally segregates into a plurality of layers or xe2x80x9cbandsxe2x80x9d which respectively serve the requirements of different types of traffic. This natural division of a network into service bands is well understood and has been widely discussed in the relevant literature.
A challenge in network management is designing network routing and admission controls to manage the service bands in a multi-class network to efficiently accommodate fluctuating service demands. It is well understood that while total network traffic may change relatively slowly over time, the traffic mix in a multi-class network may fluctuate rapidly and unpredictably. To date, efficient methods of accommodating rapid and unpredictable fluctuations in traffic service demand have eluded network designers and traffic managers. There therefore exists a need for a multi-service, multi-class digital network and methods for controlling the network which can accommodate the increasing demand for digital services without unreasonable investment in network infrastructure.
It is an object of the invention to provide a method of controlling traffic admission and routing in a multi-class digital network wherein admission control is performed by computing an equivalent bit rate for each network admission request at a node in the network and traffic admission is based on the equivalent bit rate.
It is yet a further object of the invention to provide a novel method of computing an equivalent bit rate for a traffic admission request which significantly reduces computational effort in nodes subsequently to an edge node which receives the request.
It is yet a further object of the invention to provide a method of controlling traffic admission and routing in a multi-class digital network which supports a plurality of routing schemes.
It is yet a further object of the invention to provide a method of controlling traffic admission and routing in a multi-class digital network in which routing schemes are linked to classes of service.
It is yet a further object of the invention to provide a link controller for a transport link in a multi-class digital network which stores a sampling frequency for each class of service being served at any given time by the link controller to ensure that the class of service is guaranteed a minimum service rate.
It is another object of the invention to provide a method of distributed control of a multi-class digital network in which traffic normally allocated to a path is overflowed to a connection if the path is filled to capacity.
It is a further object of the invention to provide a method of distributed control of a multi-class digital network in which traffic belonging to a class that is normally served by connection is server by a path if the path is temporarily idle.
It is yet another object of the invention to provide a method of distributed control of a multi-class digital network in which connectionless traffic without a quality of service guarantee is transported in time slots not used by other traffic having a guaranteed quality of service.
In accordance with a further aspect of the invention there is provided a method of controlling traffic admission and routing in a multi-class digital network serving variable-size packets, comprising steps of:
computing an equivalent bit rate for each traffic admission request as received at a node in the network;
determining whether a connection for the traffic admission request can be established through the network;
in an instance when a connection can be established, adding the equivalent bit rate for the traffic admission request to a current service rate allocation of a class of traffic being served by an egress link through which the connection is established, to permit a service rate controller to control transmission of each class of traffic on the egress link.
The invention further provides a link controller for a transport link in a multi-class digital network serving variable-length packets, comprising:
a service rate controller adapted to control an egress of digital traffic on the link, the service rate controller comprising a fair combinatorial circuit which includes for each class:
a) a sampling frequency memory for storing a sampling frequency computed by a node control element in response to a traffic load for the class at a specific point in time;
b) an adder adapted to add a value of the sampling frequency memory to an adder memory after counting a predetermined number of clock signals;
c) a comparator adapted to compare a value in the adder memory to a normalized packet size;
d) a selector for visiting each comparator and writing a class number to a ready queue when the comparator determines that the value in the adder memory is greater than or equal to the normalized packet size; and
e) a buffer for each class, the buffers storing packets to be transferred onto the link when the class number reaches a head of the ready queue.
The multi-class digital network in accordance with the invention distributes the network processing load between a network control element which handles global functions that are best performed at the network level and traffic functions which are best performed in a distributed fashion at the node level of the network. This distribution of functionality minimizes computational effort and maximizes transmission efficiency.
The network control element in accordance with the invention receives traffic intensity and network state information from the nodes in the network which periodically report such information to the network control element. Using the network state information, the network control element maintains a network topology. The network topology and the traffic intensity data are used by the network control element to compute network traffic routing sets which are identified to the nodes along with an order of preference. The computed routing sets are distributed to the network nodes and used by the network nodes in processing traffic admission requests.
The network nodes include node control elements which control traffic admission, traffic routing and the computation of service-rate allocations for classes of traffic served by egress links at the node.
Edge network node control elements receive traffic admission requests from subtending sources. The edge node control elements compute an equivalent bit rate for each traffic admission request based on a novel method in accordance with the invention. In order to minimize further processing when it is necessary to establish a connection across the network, the edge node control element also computes variables which enable subsequent nodes involved in the connection to rapidly compute an approximate equivalent bit rate used in route selection.
The multi-class digital network in accordance with the invention preferably supports a plurality of digital services which may require different transport modes, each transport mode consisting of at least one transport protocol. Since the packets of the same protocol may be of variable size, a link controller is provided which accommodates variable packet sizes so that packets need not be disassembled and converted to a standard format by edge device interfaces.
The multi-class digital network adopts a service-rate discipline comprising a guaranteed minimum rate per class in order to ensure efficient use of the network while meeting transmission rate and quality of service commitments. In order to minimize computing requirements for routing, high-frequency, low bit-rate traffic is preferably served by paths commonly referred to as direct routes set up through the network. High bit-rate connection-oriented traffic is preferably served by connections set up on demand. Each service type is preferably assigned to at least one class and each class is preferably assigned to a separate band in the network. The bands are dynamically configured and have elastic boundaries which fluctuate with traffic load. Unused time slots accept traffic from any waiting source in a predetermined hierarchical order in which connectionless traffic without a quality of service is served last.